#include<bits/stdc++.h>
using namespace std;
int maxv[maxn*20]; 
long long read(){
    long long x;
    scanf("%lld",&x);
    return x;
}
long long IN(){
    long long a=0;
    char ch;
    while((ch=getchar())!=' '&&ch!='\n'){
        a*=10;
        a+=ch-'0';
    }
    return a;
}
struct segment_tree{
	int s[maxn];
	int ql,qr,n,p,v;
	void init(int n){
		for(int i=1;i<=maxn;i++)maxv[i]=inf;
		memset(s,0,sizeof(s));
		this->n=n;
	}
	int _query(int o,int L,int R){
		int ans=-inf;
		int mid=(L+R)>>1;
		if(ql<=L&&qr>=R) return maxv[o];  
		if(mid>=ql) ans=max(ans,_query(o<<1,L,mid));  
		if(mid<qr) ans=max(ans,_query((o<<1)+1,mid+1,R));  
		return ans;
	}
	int query(int l,int r){
		ql=l;qr=r;
		return _query(1,1,n);
	}
	void _update(int o,int L,int R){
		int mid=(L+R)>>1;
		if(L==R)maxv[o]=v;
		else {
			if(p<=mid)_update((o<<1),L,mid);
			else _update((o<<1)+1,mid+1,R);
			maxv[o]=max(maxv[o<<1],maxv[(o<<1)+1]);  
		}
	}
	int update(int x,int y){
		s[x]=y;   
		p=x;v=y; _update(1,1,n);
	}
	void build(int o,int L,int R){  
		int mid=(L+R)>>1;
		if(L==R) maxv[o]=s[L];
		else {
			build((o<<1),L,mid); build((o<<1)+1,mid+1,R);  
			maxv[o]=max(maxv[o<<1],maxv[(o<<1)+1]);  
		}
	}
};
segment_tree tree;
int main(){
	long long n=read(),m=read();
	tree.init(n);
	for(int i=1;i<=n;i++)_read(tree.s[i]);
	tree.build(1,1,n);
	while(m--){
		int k,x,y;
		_read(k);_read(x);_read(y);
		if(k==1)tree.update(x,tree.s[x]+y);
		else printf("%d\n",tree.query(x,y));
	}
}